package DisjointSetUnion;

public class DisjointSetUnion {

    public static int MAXN = 100_0001;
    public static int[] father = new int[MAXN];
    public static int[] size = new int[MAXN];
    public static int[] stack = new int[MAXN];
    public static int n;


    public static void build() {
        // 初始化，所有元素的父节点都是自己，且所属集合大小为1，因为只有自己
        for (int i = 0; i <= n; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    public static int find(int i) {
        // 沿途收集了几个点
        int size = 0;
        while (i != father[i]) {
            stack[size++] = i;
            i = father[i];
        }

        // 扁平化，把收集到的节点的父节点都改为代表节点
        while (size > 0) {
            father[stack[--size]] = i;
        }
        return i;
    }

    public static boolean isSameSet(int x, int y) {
        return find(x) == find(y);
    }

    public static void union(int x, int y) {
        int fatherOfX = find(x);
        int fatherOfY = find(y);
        if (fatherOfX != fatherOfY) {
            if (size[fatherOfX] >= size[fatherOfY]) {
                size[fatherOfX] += size[fatherOfY];
                father[fatherOfY] = fatherOfX;
            } else {
                size[fatherOfY] += size[fatherOfX];
                father[fatherOfX] = fatherOfY;
            }
        }
    }
}
